# 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
#
#  示例 1：
# 输入：nums = [1,5,11,5]
# 输出：true
# 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
#
#  示例 2：
# 输入：nums = [1,2,3,5]
# 输出：false
# 解释：数组不能分割成两个元素和相等的子集。
from typing import List


class Solution:
    def canPartition2(self, nums: List[int]) -> bool:
        """
        该问题可转为在nums中是否存在若干元素之和为 numSum // 2 (也就是 0-1 背包问题)
        于是可以用动态规划解决
        dp[i][j]表示 nums[0:i + 1](即nums的前 i 个元素) 之中是否存在若干元素之和(元素可以不选完)为 j 的组合
        :param nums:
        :return:
        """
        numSum, numSize = sum(nums), len(nums)
        if numSum % 2 != 0 or (target := numSum // 2) < max(nums):
            return False
        dp = [[False] * (target + 1) for _ in range(numSize)]

        dp[0][nums[0]] = True  # 初始状态
        for i in range(numSize):  # 初始状态
            dp[i][0] = True

        for i in range(1, numSize):
            curNum = nums[i]
            for j in range(1, target + 1):
                if j >= curNum:  # j >= nums[i]，则对于当前的数字 nums[i]，可以选取也可以不选取，两种情况只要有一个为true 就是true
                    dp[i][j] = dp[i - 1][j - curNum] or dp[i - 1][j]  # 前者表示选择nums[i]的结果，后者表示不选的结果
                else:
                    dp[i][j] = dp[i - 1][j]
        return dp[-1][-1]

        # # 空间优化
        # # 很容易发现当前值只与上一行的状态值有关，且最终结果只需要最后一行，所以可以进行空间优化
        # dp = [True] + [False] * target
        # # 每一行的结果需要从大到小计算，因为如果从小到大更新 dp 值，那么在计算 dp[j] 值的时候，
        # # dp[j−nums[i]] 已经是被更新过的状态，不再是上一行的 dp 值了
        # for i, num in enumerate(nums):
        #     for j in range(target, num - 1, -1):
        #         dp[j] |= dp[j - num]
        # return dp[target]

    def canPartition1(self, nums: List[int]) -> bool:
        """
        对于每个元素有选择该元素和不选两种可能
        选择i位置，递归找新目标数target-nums[i]， 或者不选择i位置，在后面位置找target
        (超时)
        :param nums:
        :return:
        """
        size, numSum = len(nums), sum(nums)

        def find(index: int, target: int) -> bool:
            if index == size:
                return target == 0
            if target - nums[index] == 0:
                return True
            return find(index + 1, target - nums[index]) or find(index + 1, target)  # 前者是选择当前元素，后者是不选当前元素

        if numSum % 2 != 0 or max(nums) > numSum // 2:
            return False
        return find(0, numSum // 2)

    def canPartition(self, nums: List[int]) -> bool:
        return self.canPartition1(nums)


if __name__ == "__main__":
    nums = [1, 5, 11, 5]
    nums = [1, 2, 3, 5]
    print(Solution().canPartition(nums))
